/**
 * 给定数组A，Q个操作，询问有2种：
 * 1. 单点修改
 * 2. [L, R], 在[L, R]中选择一段(长度至少是2)，记作[i, j]，再把[i, j]分成两段
 *    要求前一段减去后一段之差最大
 * 考虑到数组A均为正数，因此[i, j]必然是[L, j]，且分段必然是[L, j-1]与[j, j]
 * 于是差变为了 S[L...j-1] - Aj
 * 再考虑将其改为 S[j - 1] - Aj - S[L-1]
 * 用线段树维护 Qj = S[j-1] - Aj 的最大值
 * 用树状数组维护 S[L-1] 前缀和
 * 对于单点修改操作 1 p newValue，首先求出delta
 * 在线段树上将p位置增加delta，将[p+1, N]位置增加-delta
 * 树状数组正常操作即可
 * 查询操作的话，在线段树上查询[L + 1, R]，再减去S[L-1]即可
 */
#include <bits/stdc++.h>
using namespace std;

struct FenwickTree{ // 树状数组

using value_type = long long int;
using vec_type = vector<value_type>;

int n;
vec_type c;

FenwickTree() = default;

static int lowbit(int x){return x & -x;}

void init(int nn){this->c.assign((this->n=nn) + 1, 0);}

void modify(int pos, value_type delta){
    for(int i=pos;i<=this->n;i+=lowbit(i)) this->c[i] += delta;
}

value_type query(int pos)const{
    value_type ans = 0;
    for(int i=pos;i;i-=lowbit(i)) ans += this->c[i];
    return ans;
}

value_type query(int s, int e)const{return this->query(e) - this->query(s - 1);}

};


struct SegTree{ // 线段树带延迟

using llt = long long;

int N;

using value_type = llt;
vector<value_type> data; // 线段树

using lazy_type = llt;
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    return max(ls, rs);
}

/// 从上往下计算信息，要变动
void _dn_(int t, int s, int e, const lazy_type & delta) {
    // assert(0);
    data[t] += delta;
    lazy[t] += delta;
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int a, int b, const lazy_type & delta){
    _modify(1, 1, N, a, b, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 这个函数不用动
void build(int n) {
    _build(1, 1, n);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    value_type ans = -(0x7F8F9FAFBFCFDFEF);
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int a, int b, const lazy_type & delta) {
    if(a <= s and e <= b) {
        _dn_(t, s, e, delta);
        return;
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    if(a <= mid) _modify(lson(t), s, mid, a, b, delta);
    if(mid < b) _modify(rson(t), mid + 1, e, a, b, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 这个函数几乎不用动
void _pushDown(int t, int s, int e) {
    if(lazy_zero() == lazy[t]) return;
    auto & lz = lazy[t];
    auto ls = lson(t), rs = rson(t);
    int mid = (s + e) >> 1;

    _dn_(ls, s, mid, lz);
    _dn_(rs, mid + 1, e, lz);

    lz = lazy_zero();
}


/// 几乎不用动
void _build(int t, int s, int e) {
    if(s == e) {
        int x; cin >> x;
        data[t] = value_type(x); // 注意提供value_type的初始化
        return; 
    }
    int mid = (s + e) >> 1;
    _build(lson(t), s, mid);
    _build(rson(t), mid + 1, e);
    _pushUp(t);
}

/// 辅助函数，视延迟的类型而变动
static const lazy_type & lazy_zero() {
    static const lazy_type LAZY0 = 0;
    return LAZY0; 
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0 = 0;
    return VALUE0;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};



using llt = long long;
using vi = vector<int>;

llt const INF = 0x7F8F9FAFBFCFDFEF;

int N;
int Q;
FenwickTree Bt;
SegTree St;
vector<llt> A;

void modify(int pos, int newValue){
    auto cha = newValue - A[pos];
    A[pos] = newValue;

    if(pos > 1){
        St.modify(pos, pos, -cha);
    }
    St.modify(pos + 1, N, cha);
    Bt.modify(pos, cha);
    return;
}

void proc(){
    for(int c,x,y,q=1;q<=Q;++q){
        cin >> c >> x >> y;
        if(1 == c){
            modify(x, y);
        }else{
            auto ans = St.query(x + 1, y);
            cout << ans - Bt.query(x - 1) << "\n";
        }
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1; 
    cin >> nofkase;
    while(nofkase--){
        cin >> N >> Q;
        A.assign(N + 1, {});
        Bt.init(N);
        St.init(N);
        llt s = 0;
        for(int a,i=1;i<=N;++i){
            cin >> a;
            Bt.modify(i, A[i] = a);
            if(1 == i){
                St.modify(i, i, -INF);
            }else{
                St.modify(i, i, s - a);
            }
            
            s += a;
        }
        proc();
    }
    return 0;
}